#include <vector>
#include <algorithm>

using namespace std;


class Solution {
public:
    // 双重循环 + 双指针 (参考 ThreeSum)
    // 确保了跳过重复数值，因此答案中不会有重复
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        if (n < 4) return res;
        sort(nums.begin(), nums.end());  // takes space O(log(n))

        // 添加了剪枝操作
        for (int i=0; i<n-3; ++i) {
            if (i>0 && nums[i]==nums[i-1]) continue;  // 重复数值跳过
            for (int j=i+1; j<n-2; ++j) {
                if (j>i+1 && nums[j]==nums[j-1]) continue;  // 重复数值跳过
                int l = j + 1, r = n - 1;
                while (l < r) {
                    // int sum = nums[i]+nums[j]+nums[l]+nums[r];  // signed integer overflow!
                    if (nums[i]+nums[j]+nums[l]+nums[r] > target) {
                        while (l<r && nums[r]==nums[--r]);  // 先改变，并且跳过重复数值
                    } else if (nums[i]+nums[j]+nums[l]+nums[r] < target) {
                        while (l<r && nums[l]==nums[++l]);  // 先改变，并且跳过重复数值
                    } else {
                        res.push_back(vector<int>{nums[i], nums[j], nums[l], nums[r]});
                        while (l<r && nums[l]==nums[++l]);  // 先改变，并且跳过重复数值
                        while (l<r && nums[r]==nums[--r]);  // 先改变，并且跳过重复数值
                    }
                }
            }
        }
        
        return res;
    }
};
